{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Binary Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countBinarySubstrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #计数二进制子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串&nbsp;<code>s</code>，统计并返回具有相同数量 <code>0</code> 和 <code>1</code> 的非空（连续）子字符串的数量，并且这些子字符串中的所有 <code>0</code> 和所有 <code>1</code> 都是成组连续的。</p>\n",
    "\n",
    "<p>重复出现（不同位置）的子串也要统计它们出现的次数。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"00110011\"\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>6 个子串满足具有相同数量的连续 1 和 0 ：\"0011\"、\"01\"、\"1100\"、\"10\"、\"0011\" 和 \"01\" 。\n",
    "注意，一些重复出现的子串（不同位置）要统计它们出现的次数。\n",
    "另外，\"00110011\" 不是有效的子串，因为所有的 0（还有 1 ）没有组合在一起。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"10101\"\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>有 4 个子串：\"10\"、\"01\"、\"10\"、\"01\" ，具有相同数量的连续 1 和 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code> 为 <code>'0'</code> 或 <code>'1'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-binary-substrings](https://leetcode.cn/problems/count-binary-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-binary-substrings](https://leetcode.cn/problems/count-binary-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"00110011\"', '\"10101\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        pre, cur, res, prec = 0, 1, 0, s[0]\n",
    "        for c in s[1:]:\n",
    "            if c != prec: pre, cur = cur, 1\n",
    "            else: cur += 1\n",
    "            if cur <= pre: res += 1\n",
    "            prec = c\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        m = re.findall('[0]+|[1]+',s)\n",
    "        return sum([min(len(m[i]),len(m[i+1])) for i in range(len(m)-1)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        res = []\n",
    "        pre = ''\n",
    "        ans = 0\n",
    "        for i in s:\n",
    "            if pre == '' or i == pre[-1]:\n",
    "                pre += i\n",
    "            else:\n",
    "                res.append(pre)\n",
    "                pre = i\n",
    "        if pre:\n",
    "            res.append(pre)\n",
    "        for i in range(len(res)-1):\n",
    "            ans += min([len(res[i]),len(res[i+1])])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        count, pre_count = 1, 1\n",
    "        res = 0\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == s[i - 1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                pre_count = count\n",
    "                count = 1\n",
    "            if pre_count >= count:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        char_list=[s[0]]\n",
    "        freq_list=[1]\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]!=s[i-1]:\n",
    "                char_list.append(s[i])\n",
    "                freq_list.append(1)\n",
    "            else:\n",
    "                freq_list[-1]+=1\n",
    "        if len(char_list)<=1:\n",
    "            return 0\n",
    "        else:\n",
    "            ret=0\n",
    "            for i in range(len(char_list)-1):\n",
    "                ret+=min(freq_list[i],freq_list[i+1])\n",
    "            return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        pre, cur, count = 0,1,0\n",
    "        n = len(s)\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "        for i in range(1, n):\n",
    "            if s[i-1] == s[i]:\n",
    "                cur += 1\n",
    "            else:\n",
    "                pre = cur\n",
    "                cur = 1\n",
    "            if pre>=cur:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        a = s[0]\n",
    "        num = 1\n",
    "        b = [0] * len(s)\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == a:\n",
    "                num += 1\n",
    "            else:\n",
    "                pre = num\n",
    "                num =1\n",
    "                a = s[i]\n",
    "                b.append(pre)\n",
    "        b.append(num)\n",
    "        return sum(min(c,d) for c,d in zip(b, b[1:]))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        res, m, n, pre = 0, 0, 0, \"\"\n",
    "        for si in s:\n",
    "            if pre and pre != si:\n",
    "                res += min(m-n, n)\n",
    "                m, n = n, 0\n",
    "            pre = si\n",
    "            m, n = m+1, n+1\n",
    "        res += min(m-n, n) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        # ser = []\n",
    "        # cnt = 1\n",
    "        # s += '2'\n",
    "        # for i in range(len(s)-1):\n",
    "        #     if s[i] == s[i+1]:\n",
    "        #         cnt += 1\n",
    "        #     else:\n",
    "        #         ser.append(cnt)\n",
    "        #         cnt = 1\n",
    "        # return 0 if len(ser) == 1 else sum(min(ser[i],ser[i+1]) for i in range(len(ser)-1))\n",
    "\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i<len(s):\n",
    "            j = i\n",
    "            cnt = 0\n",
    "            while j<len(s) and s[j]==s[i]:\n",
    "                cnt += 1\n",
    "                j += 1\n",
    "            k = j\n",
    "            while k<len(s) and s[k]!=s[i] and cnt>0:\n",
    "                cnt -= 1\n",
    "                k += 1\n",
    "\n",
    "            res += j-i-cnt\n",
    "            i = j\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        pre = \"\"\n",
    "        res = 0\n",
    "        m, n = 0, 0\n",
    "        for si in s:\n",
    "            if pre and pre != si:\n",
    "                res += min(m-n, n)\n",
    "                m, n = n, 0\n",
    "            pre = si\n",
    "            m += 1\n",
    "            n += 1\n",
    "\n",
    "        res += min(m-n, n) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        # 回顾 数学\n",
    "        num0 = 0\n",
    "        num1 = 1\n",
    "        res = 0\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i]==s[i+1]:\n",
    "                num1 += 1\n",
    "            else:\n",
    "                res += min(num0,num1)\n",
    "                num0 = num1\n",
    "                num1 = 1\n",
    "        res += min(num0,num1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        a=len(s)\n",
    "        b=[]\n",
    "        for i in range(0,a):\n",
    "            if i==0:\n",
    "                b.append(1)\n",
    "            elif s[i]==s[i-1]:\n",
    "                b[-1]+=1\n",
    "            else:\n",
    "                b.append(1)\n",
    "        a=[min(x,y) for x,y in zip(b[1:],b[:-1])]\n",
    "        return sum(a)\n",
    "\n",
    "\n",
    "\n",
    "     \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        s=list(s)\n",
    "        n=len(s)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        count=1\n",
    "        res=[]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if s[i-1]==s[i]:\n",
    "                count+=1\n",
    "            else: \n",
    "                res.append(count)\n",
    "                count=1\n",
    "        res.append(count)\n",
    "\n",
    "        m=len(res)\n",
    "        if m==1:\n",
    "            return 0\n",
    "\n",
    "        ans=0\n",
    "        for j in range(1,len(res)):\n",
    "            ans+=min(res[j-1],res[j])\n",
    "\n",
    "        print(res)\n",
    "\n",
    "        \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        pre,cur=0,1\n",
    "        ans=0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]==s[i-1]:\n",
    "                cur+=1\n",
    "            else:\n",
    "                if pre:\n",
    "                    ans+=min(pre,cur)\n",
    "                pre,cur=cur,1\n",
    "        \n",
    "        return ans+min(pre,cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i] != s[i + 1]:\n",
    "                ans += 1\n",
    "                l_dt, r_dt = s[i], s[i + 1]\n",
    "                left, right = i-1, i + 2\n",
    "                while(left >= 0 and right <= len(s) - 1):\n",
    "                    if s[left] == l_dt and s[right] == r_dt:\n",
    "                        ans += 1\n",
    "                        left -= 1\n",
    "                        right += 1\n",
    "                    else:\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        # n = len(s)\n",
    "        # zero = [0]*n\n",
    "        # one = [0]*n\n",
    "        # for i,ele in enumerate(s):\n",
    "        #     if (i == 0):\n",
    "        #         if (ele == '0'):\n",
    "        #             zero[0] = 1\n",
    "        #         else:\n",
    "        #             one[0] = 1\n",
    "        #         continue\n",
    "\n",
    "        #     if ele == '0':\n",
    "        #         zero[i] = zero[i-1] + 1\n",
    "        #     else:\n",
    "        #         zero[i] = zero[i-1]\n",
    "        #     if ele == '1':\n",
    "        #         one[i] += one[i-1] + 1\n",
    "        #     else:\n",
    "        #         one[i] = one[i-1]\n",
    "        # print(one)\n",
    "        # print(zero)\n",
    "        # res = 0\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+1,n,1):\n",
    "\n",
    "        #         a_1,b_1 = one[i-1] if i>=1 else 0,one[j]\n",
    "        #         a_0,b_0 = zero[i-1] if i>=1 else 0, zero[j]\n",
    "        #         if (b_1-a_1 == b_0 - a_0):\n",
    "        #             print(i,j)\n",
    "        #             res +=1\n",
    "        # return res\n",
    "\n",
    "\n",
    "\n",
    "        #必须都是成组连续的\n",
    "        #那其实就确实很简单了\n",
    "        flag = s[0]\n",
    "        one = 1 if flag == '1' else 0\n",
    "        zero = 1 if flag == '0' else 0\n",
    "        res = 0\n",
    "\n",
    "        for i,ele in enumerate(s):\n",
    "            if (i==0):\n",
    "                continue\n",
    "            if (ele == flag and ele == '1'):\n",
    "                one+=1\n",
    "            if (ele == flag and ele == '0'):\n",
    "                zero+=1\n",
    "            if (ele !=flag and ele == '0'):\n",
    "                flag = ele\n",
    "                zero = 1\n",
    "            if (ele != flag and ele == '1'):\n",
    "                flag =ele\n",
    "                one = 1\n",
    "            if (flag == '1' and one <= zero):\n",
    "                res += 1\n",
    "            if (flag == '0' and zero<=one):\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i<len(s):\n",
    "            j = i\n",
    "            cnt = 0\n",
    "            while j<len(s) and s[j]==s[i]:\n",
    "                cnt += 1\n",
    "                j += 1\n",
    "            k = j\n",
    "            while k<len(s) and s[k]!=s[i] and cnt>0:\n",
    "                cnt -= 1\n",
    "                k += 1\n",
    "\n",
    "            res += j-i-cnt\n",
    "            i = j\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        pre, cur = 0, 0\n",
    "        ans = 0\n",
    "        ch = None\n",
    "        for x in s:\n",
    "            if ch == None or ch != x:\n",
    "                ans = ans + min(pre, cur)\n",
    "                ch = x\n",
    "                pre = cur\n",
    "                cur = 1\n",
    "            else:\n",
    "                cur += 1\n",
    "        return ans+min(pre, cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        res=0\n",
    "        prev=0\n",
    "        cur=0\n",
    "        for i in range(n):\n",
    "            if i==0:\n",
    "                cur=1\n",
    "            elif s[i]==s[i-1]:\n",
    "                cur+=1\n",
    "            else:\n",
    "                res+=min(prev,cur)\n",
    "                prev=cur\n",
    "                cur=1\n",
    "        res+=min(prev,cur)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        def helper(left,right):\n",
    "            cnt=1\n",
    "            while left>0 and right<len(s)-1 and s[left]==s[left-1] and s[right]==s[right+1]:\n",
    "                cnt+=1\n",
    "                left-=1\n",
    "                right+=1\n",
    "            return cnt\n",
    "\n",
    "        n=len(s)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        res=0\n",
    "        for i in range(n-1):\n",
    "            if s[i]!=s[i+1]:\n",
    "                res+=helper(i,i+1)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # O(N)\n",
    "    # def countBinarySubstrings(self, s: str) -> int:\n",
    "    #     ans = 0\n",
    "    #     tmp = []\n",
    "    #     count = 1\n",
    "    #     for i in range(1, len(s)):\n",
    "    #         if s[i] != s[i-1]:\n",
    "    #             tmp.append(count)\n",
    "    #             count = 1\n",
    "    #         else:\n",
    "    #             count += 1\n",
    "    #     tmp.append(count)   # 加入最后一次的\n",
    "    #     for i in range(1, len(tmp)):\n",
    "    #         ans += min(tmp[i-1], tmp[i])  # 相邻之间能符合条件的次数就是二者少的那个\n",
    "    #     return ans\n",
    "    # 空间O(1)\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        count = 1\n",
    "        last = 0\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] != s[i-1]:\n",
    "                if (last):\n",
    "                    ans += min(last, count)\n",
    "                last = count\n",
    "                count = 1\n",
    "            else:\n",
    "                count += 1\n",
    "        ans += min(count, last)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        jk=[0,1]\n",
    "        count=0\n",
    "        n=len(s)\n",
    "        for i in range (1,n):\n",
    "            if s[i-1]==s[i]:\n",
    "                jk[1]+=1\n",
    "            else:\n",
    "                count+=min(jk[0],jk[1])\n",
    "                jk[0]=jk[1]\n",
    "                jk[1]=1\n",
    "        count+=min(jk[0],jk[1])\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        ser = []\n",
    "        cnt = 1\n",
    "        s += '2'\n",
    "        count = 0\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i] == s[i+1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ser.append(cnt)\n",
    "                if len(ser) == 2:\n",
    "                    count += min(ser)\n",
    "                    del ser[0]\n",
    "                cnt = 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        last = 0\n",
    "        cur = 1\n",
    "        ans = 0\n",
    "        for a, b in pairwise(s):\n",
    "            if a == b:\n",
    "                cur += 1\n",
    "            else:\n",
    "                ans += min(last, cur)\n",
    "                last = cur\n",
    "                cur = 1\n",
    "        return ans + min(last, cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        cur=1\n",
    "        last=0\n",
    "        count=0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]==s[i-1]:\n",
    "                cur+=1\n",
    "            else:\n",
    "                last=cur\n",
    "                cur=1\n",
    "            if last>=cur:\n",
    "                count+=1\n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        prev, mid, res = 0, -1, 0\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] != s[i-1]:\n",
    "                if mid != -1:\n",
    "                    prev = mid\n",
    "                mid = i\n",
    "                res += 1\n",
    "            else:\n",
    "                if mid != -1 and i - mid + 1 <= mid - prev:\n",
    "                    res += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        pre, cur = 0, 1\n",
    "        res = 0\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == s[i-1]:\n",
    "                cur += 1\n",
    "            else:\n",
    "                pre = cur\n",
    "                cur = 1\n",
    "            if pre >= cur:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        # 暴力\n",
    "        # res = 0\n",
    "        # n = len(s)//2\n",
    "        # for i in range(1,n+1,1):\n",
    "        #     p1 = '0'*i+'1'*i\n",
    "        #     res += s.count(p1)\n",
    "        #     p2 = '1'*i+'0'*i\n",
    "        #     res += s.count(p2)\n",
    "        #     if s.count(p1) == 0 and s.count(p2) == 0:\n",
    "        #         break\n",
    "        # return res\n",
    "\n",
    "        # 指针p，左侧字段连续值cntl，右侧字段连续值cntr\n",
    "        res = 0\n",
    "        p = s[0]\n",
    "        cntl = 0\n",
    "        cntr = 0\n",
    "        # s字段增添'停止'字符作为判断\n",
    "        s += '-'\n",
    "        for i in s:\n",
    "            if i != p:\n",
    "                p = i\n",
    "                res += min(cntl,cntr)\n",
    "                cntl = cntr\n",
    "                cntr = 0\n",
    "            if i == p:\n",
    "                cntr += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        cur=1\n",
    "        last=0\n",
    "        count=0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]==s[i-1]:\n",
    "                cur+=1\n",
    "            else:\n",
    "                last=cur\n",
    "                cur=1\n",
    "            if last>=cur:\n",
    "                count+=1\n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i<len(s):\n",
    "            j = i\n",
    "            cnt = 0\n",
    "            while j<len(s) and s[j]==s[i]:\n",
    "                cnt += 1\n",
    "                j += 1\n",
    "            k = j\n",
    "            while k<len(s) and s[k]!=s[i] and cnt>0:\n",
    "                cnt -= 1\n",
    "                k += 1\n",
    "\n",
    "            res += j-i-cnt\n",
    "            i = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        last = 0\n",
    "        cur = 1\n",
    "        ans = 0\n",
    "        for a, b in pairwise(s):\n",
    "            if a == b:\n",
    "                cur += 1\n",
    "            else:\n",
    "                last = cur\n",
    "                cur = 1\n",
    "            if last:\n",
    "                ans += 1\n",
    "                last -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        j = 0\n",
    "        ret = 0\n",
    "        last = None\n",
    "        # inter = []\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == s[i-1]:\n",
    "                continue\n",
    "            else:\n",
    "                if last is not None:\n",
    "                    ret += min(len(last), i-j)\n",
    "                last = s[j:i]\n",
    "                # inter.append(last)\n",
    "                j = i\n",
    "        if last is not None:\n",
    "            ret += min(len(last), len(s)-j)\n",
    "        last = s[j:]\n",
    "        # inter.append(last)\n",
    "        # print(inter)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        count0=0\n",
    "        count1=0\n",
    "        ans=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='0':\n",
    "                count0+=1\n",
    "            else:\n",
    "                count1+=1\n",
    "            if i<len(s)-1 and s[i]!=s[i+1] and count0 and count1:\n",
    "                ans+=min(count0,count1)\n",
    "                if s[i+1]=='0':\n",
    "                    count0=0\n",
    "                else:\n",
    "                    count1=0\n",
    "        return ans+min(count0,count1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        ser = []\n",
    "        cnt = 1\n",
    "        s += '2'\n",
    "        count = 0\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i] == s[i+1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ser.append(cnt)\n",
    "                if len(ser) == 2:\n",
    "                    count += min(ser)\n",
    "                    del ser[0]\n",
    "                cnt = 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        cnt = [0,0]     #记录当前有效数组中的0,1数量\n",
    "        tail = int(s[0])\n",
    "        res = 0\n",
    "        cnt[tail] += 1\n",
    "        for i in s[1:]:\n",
    "            i = int(i)\n",
    "            if tail == i:\n",
    "                cnt[i] += 1\n",
    "            else:\n",
    "                cnt[i] = 1\n",
    "                tail = i\n",
    "            if cnt[i] <= cnt[1-i]:\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "\n",
    "        ptr = 0\n",
    "        n = len(s)\n",
    "        last = 0\n",
    "        res = 0\n",
    "\n",
    "        while ptr < n:\n",
    "\n",
    "            c = s[ptr]\n",
    "            count = 0\n",
    "            while ptr < n and s[ptr] == c:\n",
    "                ptr += 1\n",
    "                count += 1\n",
    "\n",
    "            res += min(count, last)\n",
    "            last = count\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        count=0\n",
    "        cnt=0\n",
    "        ans=0\n",
    "        for i in range(len(s)):\n",
    "            cnt+=1\n",
    "            if i<len(s)-1 and s[i]!=s[i+1]:\n",
    "                ans+=min(count,cnt)\n",
    "                count=cnt\n",
    "                cnt=0\n",
    "        return ans+min(count,cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        '''\n",
    "        官方题解思路是先通过计数分割字符串，比如00110，分割结果就是counts = [2, 2, 1]，然后再对counts两两取最小值求和即为结果\n",
    "        '''\n",
    "        seq = [0, 1]\n",
    "        res = []\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == s[i-1]:\n",
    "                seq[1] += 1\n",
    "            else:\n",
    "                res.append(min(seq))\n",
    "                seq[0] = seq[1]\n",
    "                seq[1] = 1\n",
    "        res.append(min(seq))\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        res = 0\n",
    "        pre = [0, 1]\n",
    "\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i] != s[i+1]:\n",
    "                pre.append(1)\n",
    "                res += 1\n",
    "            else:\n",
    "                pre[-1] += 1\n",
    "                if pre[-1] <= pre[-2]:\n",
    "                    res += 1\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        count = 0\n",
    "        def extendstring(s,start,end):\n",
    "            nonlocal count\n",
    "            while start >=0 and end <= len(s) - 1 and s[start] != s[end]:\n",
    "                if end - start == 1:\n",
    "                    start -= 1\n",
    "                    end += 1\n",
    "                    count +=1\n",
    "                else:\n",
    "                    if s[end] != s[end - 1]:\n",
    "                        break\n",
    "                    else:\n",
    "                        start -= 1\n",
    "                        end += 1\n",
    "                        count +=1\n",
    "        for i in range(len(s)):\n",
    "            extendstring(s, i, i+1)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        m = re.findall('[0]+|[1]+', s)\n",
    "    # 取m中相邻元素的长度小值为000..1111...的个数， 然后全部取sum就是全部\n",
    "        return sum([min(len(m[i]), len(m[i + 1])) for i in range(len(m) - 1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        pre=s[0]\n",
    "        cnt=0\n",
    "        pool=[]\n",
    "        for c in s:\n",
    "            if c==pre:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                pool.append(cnt)\n",
    "                cnt=1\n",
    "                pre=c\n",
    "        pool.append(cnt)\n",
    "        \n",
    "        ans=0\n",
    "        for i in range(len(pool)-1):\n",
    "            ans+=min(pool[i],pool[i+1])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        count =1\n",
    "        nums = []\n",
    "        for i in range(1,n):\n",
    "            if s[i] == s[i-1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                nums.append(count)\n",
    "                count =1\n",
    "        nums.append(count)\n",
    "        ans = 0\n",
    "        m = len(nums)\n",
    "        if m == 1:\n",
    "            return 0\n",
    "        for i in range(m-1):\n",
    "            ans += min(nums[i],nums[i+1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "      resList = []\n",
    "      temp = 0\n",
    "      for i in range(len(s)):\n",
    "        temp += 1\n",
    "        if i + 1 >= len(s) or s[i + 1] != s[i]:\n",
    "          resList.append(temp)\n",
    "          temp = 0\n",
    "      res = 0\n",
    "      for i in range(len(resList) - 1):\n",
    "        res += min(resList[i], resList[i+1])\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        list01 = []\n",
    "        lens = len(s)\n",
    "        if lens < 2:\n",
    "            return 0\n",
    "        j = s[0]\n",
    "        count = 1\n",
    "        for i in range(1, lens):\n",
    "            if s[i] == j:\n",
    "                count += 1\n",
    "            else:\n",
    "                list01.append(count)\n",
    "                j = str(1 - int(j))\n",
    "                count = 1\n",
    "        list01.append(count)\n",
    "\n",
    "        ans = 0\n",
    "        list01len = len(list01)\n",
    "        if list01len < 2:\n",
    "            return 0\n",
    "        for i in range(list01len-1):\n",
    "            ans += min(list01[i], list01[i+1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        temp = []\n",
    "        count = 1\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] == s[i-1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                temp.append(count)\n",
    "                count = 1\n",
    "        temp.append(count)\n",
    "        res = 0\n",
    "        for i in range(1,len(temp)):\n",
    "            res += min(temp[i-1],temp[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        group = []\n",
    "        count = 1\n",
    "        for i in range(1, len(s)):\n",
    "            if (s[i] == s[i - 1]):\n",
    "                count += 1\n",
    "            else:\n",
    "                group.append(count)\n",
    "                count = 1\n",
    "        group.append(count)\n",
    "\n",
    "        ans=0\n",
    "        for i in range(1,len(group)):\n",
    "            ans+=min(group[i],group[i-1])\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        counter = []\n",
    "        pos = 1\n",
    "        count = 1\n",
    "        while pos < len(s):\n",
    "            if s[pos] == s[pos - 1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                counter.append(count)\n",
    "                count = 1\n",
    "            pos += 1\n",
    "        counter.append(count)\n",
    "        i = 1\n",
    "        result = 0\n",
    "        while i < len(counter):\n",
    "            result += min(counter[i], counter[i - 1])\n",
    "            i +=1\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        groups = [1]\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] != s[i - 1]:\n",
    "                groups.append(1)\n",
    "            else:\n",
    "                groups[-1] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(1, len(groups)):\n",
    "            ans += min(groups[i], groups[i - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        i = 0\n",
    "        cnt = 0\n",
    "        nums = []\n",
    "        for j,char in enumerate(s):\n",
    "            if char == s[i]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                nums.append(cnt)\n",
    "                cnt = 1\n",
    "                i = j\n",
    "        nums.append(len(s)-i)\n",
    "        ans = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            ans += min(nums[i],nums[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        length=len(s)\n",
    "        temp=[];count=1\n",
    "        for i in range(length-1):\n",
    "            if s[i]==s[i+1]:\n",
    "                count+=1\n",
    "            else:\n",
    "                temp.append(count)\n",
    "                count=1\n",
    "        temp.append(count) \n",
    "        answer=0\n",
    "        for i in range(len(temp)-1):\n",
    "            answer+=min(temp[i],temp[i+1])\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        ren=[]\n",
    "        n=len(s)\n",
    "        i=0\n",
    "        while i<n:\n",
    "            start=i\n",
    "            while i<n-1 and s[i]==s[i+1]:\n",
    "                i+=1\n",
    "            ren.append(i-start+1)\n",
    "            i+=1\n",
    "        ans=0\n",
    "        for i in range(len(ren)-1):\n",
    "            ans+=min(ren[i],ren[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        counts = []\n",
    "        cnt = 1\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == s[i-1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                counts.append(cnt)\n",
    "                cnt = 1\n",
    "            if i == len(s)-1:\n",
    "                counts.append(cnt)\n",
    "        return sum(min(counts[i], counts[i-1]) for i in range(1, len(counts)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        ser = []\n",
    "        cnt = 1\n",
    "        s += '2'\n",
    "        count = 0\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i] == s[i+1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ser.append(cnt)\n",
    "                # if len(ser) == 2:\n",
    "                #     count += min(ser)\n",
    "                #     del ser[0]\n",
    "                cnt = 1\n",
    "        # return count\n",
    "        \n",
    "        return 0 if len(ser)==1 else sum(min(ser[i], ser[i+1]) for i in range(len(ser)-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        tmp = []\n",
    "        l,r = 0,0\n",
    "        re = 0\n",
    "        while l < len(s):\n",
    "            r = l+1\n",
    "            while r < len(s) and s[r] == s[l]:\n",
    "                r += 1\n",
    "            tmp.append(r-l)\n",
    "            l = r\n",
    "        for i in range(1,len(tmp)):\n",
    "            re += min(tmp[i],tmp[i-1])\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        length=len(s)\n",
    "        temp=[];count=1\n",
    "        for i in range(length-1):\n",
    "            if s[i]==s[i+1]:\n",
    "                count+=1\n",
    "            else:\n",
    "                temp.append(count)\n",
    "                count=1\n",
    "        temp.append(count) \n",
    "        answer=0\n",
    "        for i in range(len(temp)-1):\n",
    "            answer+=min(temp[i],temp[i+1])\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        num = []\n",
    "        count = 1\n",
    "        total = 0\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i+1] == s[i]:\n",
    "                count = count + 1\n",
    "            else:\n",
    "                num.append(count)\n",
    "                count = 1\n",
    "        num.append(count)\n",
    "        for k in range(len(num)-1):\n",
    "            total = total + min(num[k],num[k+1])\n",
    "        return total\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        ser = []\n",
    "        cnt = 1\n",
    "        s += '2'\n",
    "        count = 0\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i] == s[i+1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ser.append(cnt)\n",
    "                # if len(ser) == 2:\n",
    "                #     count += min(ser)\n",
    "                #     del ser[0]\n",
    "                cnt = 1\n",
    "        # return count\n",
    "        \n",
    "        return 0 if len(ser)==1 else sum(min(ser[i], ser[i+1]) for i in range(len(ser)-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        seq = [0, 1]\n",
    "        res = []\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == s[i-1]:\n",
    "                seq[1] += 1\n",
    "            else:\n",
    "                res.append(min(seq))\n",
    "                seq[0] = seq[1]\n",
    "                seq[1] = 1\n",
    "        res.append(min(seq))\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        count = list()\n",
    "        pre = s[0]\n",
    "        c = 1\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] == pre:\n",
    "                c += 1\n",
    "            else:\n",
    "                count.append(c)\n",
    "                pre = s[i]\n",
    "                c = 1\n",
    "        count.append(c)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(1, len(count)):\n",
    "            ans += min(count[i-1], count[i])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        ser = []\n",
    "        cnt = 1\n",
    "        s += '2'\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i] == s[i+1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ser.append(cnt)\n",
    "                cnt = 1\n",
    "        return 0 if len(ser) == 1 else sum(min(ser[i],ser[i+1]) for i in range(len(ser)-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        ser = []\n",
    "        cnt = 1\n",
    "        s += '2'\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i] == s[i+1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ser.append(cnt)\n",
    "                cnt = 1\n",
    "        return 0 if len(ser)==1 else sum(min(ser[i], ser[i+1]) for i in range(len(ser)-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        list=[]\n",
    "        flag=s[0]\n",
    "        cur=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==flag:\n",
    "                cur+=1\n",
    "            else:\n",
    "                if flag==\"0\":\n",
    "                    list.append(cur)\n",
    "                    flag=\"1\"\n",
    "                    cur=1\n",
    "                else:\n",
    "                    list.append(cur)\n",
    "                    flag=\"0\"\n",
    "                    cur=1\n",
    "        list.append(cur)\n",
    "        count=0\n",
    "        for i in range(len(list)-1):\n",
    "            count+=min(list[i],list[i+1])\n",
    "        return count\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        seq = [0,1]\n",
    "        res = []\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]==s[i-1]:\n",
    "                seq[1]+=1\n",
    "            else:\n",
    "                res.append(min(seq))\n",
    "                seq[0]=seq[1]\n",
    "                seq[1]=1\n",
    "        res.append(min(seq))\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        temp = []\n",
    "        for i, c in enumerate(s):\n",
    "            if i == 0 or s[i-1] != s[i]:\n",
    "                temp.append(1)\n",
    "            else:\n",
    "                temp[-1] += 1\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, len(temp)):\n",
    "            ans += min(temp[i-1], temp[i])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        ser = []\n",
    "        # tep = -1\n",
    "        cnt = 1\n",
    "        s += '2'\n",
    "        for i in range(len(s)-1):\n",
    "            # ele = ord(ele)-ord('0')\n",
    "            # if ele==tep or tep == -1:\n",
    "            #     cnt += 1\n",
    "            # if tep!=-1 or ele!=tep:\n",
    "            #     ser.append(cnt)\n",
    "            #     cnt = 0\n",
    "            # tep = ele\n",
    "            if s[i] == s[i+1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ser.append(cnt)\n",
    "                cnt = 1\n",
    "        return 0 if len(ser) == 1 else sum(min(ser[i],ser[i+1]) for i in range(len(ser)-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for si in s:\n",
    "            if stack and stack[-1] != si:\n",
    "                n = len(stack)\n",
    "                count_si = stack.count(si)\n",
    "                res += min(count_si, n-count_si)\n",
    "                stack = stack[count_si:]\n",
    "            stack.append(si)\n",
    "        if stack:\n",
    "            n = len(stack)\n",
    "            count_si = stack.count(si)\n",
    "            res += min(count_si, n-count_si) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:  \n",
    "        #每一组的长度记为c,c数据相邻的两组最小值为这两组相邻数组符合要求的子串数\n",
    "        res=0#统计满足的个数\n",
    "        c=[]\n",
    "        count=1#至少都会有一个字串\n",
    "        for i in range(1,len(s)):\n",
    "            if(s[i]==s[i-1]):\n",
    "                count+=1\n",
    "            else:\n",
    "                #先合并连续出现的字串\n",
    "                c.append(count)\n",
    "                count=1\n",
    "        c.append(count)\n",
    "        for i in range(1,len(c)):\n",
    "            res+=min(c[i-1],c[i])#计算相邻的数值\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        different_counts = []\n",
    "        count = 0\n",
    "        pre_num = s[0]\n",
    "        for n in s:\n",
    "            if n == pre_num:\n",
    "                count += 1\n",
    "            else:\n",
    "                different_counts.append(count)\n",
    "                count = 1\n",
    "                pre_num = n\n",
    "        different_counts.append(count)\n",
    "        res = 0\n",
    "        for i in range(len(different_counts) - 1):\n",
    "            res += min(different_counts[i], different_counts[i+1])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        # count the number of all continuous 0 and 1\n",
    "        count = []\n",
    "        result = 0\n",
    "        cur_str = ''\n",
    "        for c in s:\n",
    "            if c != cur_str:\n",
    "                cur_str = c\n",
    "                count.append(1)\n",
    "            else:\n",
    "                count[len(count) - 1] += 1\n",
    "        \n",
    "        # iterate through \n",
    "        if len(count) == 1:\n",
    "            return 0\n",
    "        for i in range(len(count) - 1):\n",
    "            result += min(count[i], count[i + 1])\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        seq = [0, 1]\n",
    "        res = []\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == s[i-1]:\n",
    "                seq[1] += 1\n",
    "            else:\n",
    "                res.append(min(seq))\n",
    "                seq[0] = seq[1]\n",
    "                seq[1] = 1\n",
    "        res.append(min(seq))\n",
    "        return sum(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        # transfer the binary digits into counts\n",
    "        n = len(s)\n",
    "        f = []\n",
    "        cnt = 1\n",
    "        for i in range(1, n):\n",
    "            if s[i]==s[i-1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                f.append(cnt)\n",
    "                cnt = 1\n",
    "        f.append(cnt)\n",
    "\n",
    "        # loop throught the cnts and take the mean of neighboring cnts\n",
    "        l = len(f)\n",
    "        res = 0\n",
    "        for i in range(1, l):\n",
    "            res += min(f[i], f[i-1])\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        counts = []\n",
    "        ptr, n = 0, len(s)\n",
    "        while ptr < n:\n",
    "            count_ = 0\n",
    "            ch = s[ptr]\n",
    "            while ptr < n and s[ptr] == ch:\n",
    "                ptr += 1\n",
    "                count_ += 1\n",
    "            counts.append(count_)\n",
    "        m = len(counts)\n",
    "        ans = 0 \n",
    "        for i in range(1, m):\n",
    "            ans += min(counts[i -1], counts[i])\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        state=s[0]\n",
    "        total_s=[]\n",
    "        coun=0\n",
    "        for z in s:\n",
    "            if z==state:\n",
    "                coun+=1\n",
    "            else:\n",
    "                total_s.append(coun)\n",
    "                state=z\n",
    "                coun=1\n",
    "        total_s.append(coun)\n",
    "        ans=0\n",
    "        print(total_s)\n",
    "        for i in range(len(total_s)-1):\n",
    "            ans+=min(total_s[i],total_s[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = []\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            iv = s[i]\n",
    "            ct = 0\n",
    "            while i < n and s[i] == iv:\n",
    "                ct += 1\n",
    "                i += 1\n",
    "            res.append(ct)\n",
    "\n",
    "        return sum(min(res[j], res[j - 1]) for j in range(1, len(res)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings2(self, s: str) -> int:\n",
    "        curr = ''\n",
    "        count = 0\n",
    "        counts = []\n",
    "        for c in s:\n",
    "            if c != curr:\n",
    "                curr = c\n",
    "                counts.append(count)\n",
    "                count = 1\n",
    "            else:\n",
    "                count += 1\n",
    "\n",
    "        counts.append(count)\n",
    "        print(counts)\n",
    "        ret = 0\n",
    "        for i in range(1, len(counts)):\n",
    "            ret += min(counts[i], counts[i-1])\n",
    "        return ret\n",
    "\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        curr = ''\n",
    "        count = 0\n",
    "        counts = []\n",
    "        for c in s:\n",
    "            if c != curr:\n",
    "                curr = c\n",
    "                counts.append(count)\n",
    "                count = 1\n",
    "            else:\n",
    "                count += 1\n",
    "                \n",
    "        counts.append(count)\n",
    "\n",
    "        return sum(min(counts[i], counts[i-1]) for i in range(1, len(counts)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        pre_len = 0\n",
    "        cur_len = 0\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if i==0 or s[i] == s[i-1]:\n",
    "                cur_len += 1\n",
    "            else:\n",
    "                print(pre_len, cur_len)\n",
    "                ans += min(pre_len, cur_len)\n",
    "                pre_len, cur_len = cur_len, 1\n",
    "        ans += min(pre_len, cur_len)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countBinarySubstrings(self, s: str) -> int:\r\n",
    "        n=len(s)\r\n",
    "        prev=None\r\n",
    "        counts=[]\r\n",
    "        i=0\r\n",
    "        while i<n:\r\n",
    "            count=0\r\n",
    "            prev=s[i]\r\n",
    "            while i<n and s[i]==prev:\r\n",
    "                count+=1\r\n",
    "                i+=1\r\n",
    "            counts.append(count)\r\n",
    "        \r\n",
    "        ans=0\r\n",
    "        for i in range(1,len(counts)):\r\n",
    "            ans+=min(counts[i],counts[i-1])\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBinarySubstrings(self, s: str) -> int:\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for si in s:\n",
    "            if stack and stack[-1] != si:\n",
    "                count_si = stack.count(si)\n",
    "                res += min(count_si, len(stack)-count_si)\n",
    "                stack = stack[count_si:]\n",
    "            stack.append(si)\n",
    "        if stack:\n",
    "            count_si = stack.count(si)\n",
    "            res += min(count_si, len(stack)-count_si) \n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
